import java.util.*;

/** @author Chris Howson & Steven Horsman */
class SudokuSolver
{
	/**Stores the Matrix the puzzle is stored in*/
	private Matrix puzzle;
	/**Stores the guesses made*/
	private ArrayList<SolverType> guessed = new ArrayList<SolverType>();
	/**Stores the changes made*/
	private ArrayList<SolverType> changed = new ArrayList<SolverType>();
	
	/**Sets the puzzle field to a given matrix*/
	public SudokuSolver(Matrix a)
	{
		this.puzzle = a;
	}
	
	/**Returns the list of changed items*/
	public ArrayList<SolverType> getChanged()
	{
		return changed;
	}

	/**Sets the changed field to a given array*/
	public void setChanged(ArrayList<SolverType> changed)
	{
		this.changed = changed;
	}

	/**Returns the list of guessed items*/
	public ArrayList<SolverType> getGuessed()
	{
		return guessed;
	}

	/**Sets the guessed list to a given arraylist*/
	public void setGuessed(ArrayList<SolverType> guessed)
	{
		this.guessed = guessed;
	}
	
	/**Returns the puzzle field of the matrix*/
	public Matrix getPuzzle()
	{
		return puzzle;
	}

	/**Sets the puzzle field to a given matrix*/
	public void setPuzzle(Matrix puzzle) {
		this.puzzle = puzzle;
	}

	/**Updates the puzzle's possibilities per cell*/
    void solverupdater(SolverData[][] solv, Matrix input,Boolean flag)
    {
    	int number;
    	for(int i = 0; i < this.puzzle.getRows(); i++)
    	{
    		for(int j = 0; j < this.puzzle.getCols(); j++)
    		{
    			if((int)input.getCell(i,j) != 0)
    			{
    				solv[i][j].setallfalse();
    				number = (int)this.puzzle.getCell(i,j)-1;
			  		for(int k = 0; k < 9; k++)
					{
			  			solv[i][k].setfalse(number);
					}
			   		for(int k = 0; k < 9; k++)
					{
			  			solv[k][j].setfalse(number);
			    	}
			   		int startrow = workoutstartrow(i);
					int startcol = workoutstartrow(j);
			   		for(int k = 0; k < 3; k++)
			   		{
			   			for(int l = 0; l < 3; l++)
			   			{
				  			solv[startrow+k][startcol+l].setfalse(number);
			   			}
			   		}
    			}
    		}
    	}
    }
    
    /**Checks through to see if any single possibilities*/
    Boolean solveradder(SolverData[][] solv, Matrix input)
    {
    	Boolean changed = false;
    	for(int i = 0; i < 9; i++)
    	{
    		for(int j = 0; j < 9; j++)
    		{
    			int poss = solv[i][j].getPoss();
    			if(poss == 1)
    			{
    				int changecell = solv[i][j].getOnePoss(1);
    				if(this.guessed.size()!=0) { this.changed.add(new SolverType('c',i,j,(double)changecell, null)); }
                    this.puzzle.setCell(i,j,(double)changecell);
    				changed = true;
    				return changed;
    			}

    		}
    	}
    	if(checkrowposs(solv, "row")) { return true; }
        if(checkrowposs(solv, "col")) { return true; }
        if(checkgridposs(solv)) { return true; }
    	return changed;
    }
    
    /**Changes the puzzle back to before the changes were made after a guess*/
    void revert_grid(SolverData[][] solv)
    {
    	for(int i = this.changed.size()-1; i >= 0; i--)
    	{
    		if(this.changed.get(i).getType()!='g')
    		{
    			this.puzzle.setCell(this.changed.get(i).getRow(), this.changed.get(i).getCol(), 0);
    			this.changed.remove(i);
    		}
    		else { break; }
    	}
    }
    
    /**Finds a value to guess*/
    Boolean guess(SolverData[][] solv)
    {
    	for(int i = 0; i < 9; i++)
    	{
    		for(int j = 0; j < 9; j++)
    		{
    			for(int y = 2; y < 9; y++)
    			{
    				int poss = solv[i][j].getPoss();
    				if(poss == y)
	    			{
    					int changecell;
    					changecell = solv[i][j].getOnePoss(1);
	    				this.guessed.add(new SolverType('g',i,j,(double)changecell,null));
	    				this.changed.add(new SolverType('g',i,j,(double)changecell, solv));
	    				this.puzzle.setCell(i,j,changecell);
	    				return true;
	    			}
	    		}
    		}
    	}
    		revert_grid(solv);
    		int csize = this.changed.size()-1;
    		if(csize!=-1)
    		{
	    		int crow = this.changed.get(csize).getRow();
	    		int ccol = this.changed.get(csize).getCol();
	    		int cdata = (int)this.changed.get(csize).getData();
	    		
		    	this.puzzle.setCell(crow, ccol,0);
		    	SolverData[][] solvs = this.changed.get(csize).getSolveDat();
		    	for(int i = 0;i<9;i++)
		    	{
		    		for(int j = 0;j<9;j++)
			    	{
		    			solv[i][j] = new SolverData(solvs[i][j]);
			    	}
		    	}
		    	solv[crow][ccol].setfalse(cdata-1);
		    	this.changed.remove(csize);
		    	revert_grid(solv);
    		}
    	return true;
    }
    
    /**Check whether a single solution in a 3x3 grid*/
    Boolean checkgridposs(SolverData[][] solv)
    {
        //For each of the 9 grids
        for(int i = 0; i < 9; i++)
        {
            int tot[] = {0,0,0,0,0,0,0,0,0};
            int startrow = workoutstartrow(i);
            int startcol = 0;
            if(i==0 || i==3 || i==6) { startcol = 0; }
            else if(i==1 || i==4 || i==7) { startcol = 3; }
            else if(i==2 || i==5 || i==8) { startcol = 6; }
            //For each of the 3 rows per grid
            for(int j = 0; j < 3; j++)
            {
                //For each of the 3 columns per grid
                for(int k = 0; k < 3; k++)
                {
                    //For each possible number
                    for(int l = 0; l < 9; l++)
                    {
                        if(solv[startrow+j][startcol+k].getCell(l))
                        {
                            tot[l] = tot[l]+1;
                        }
                    }
                }
            }
            for(int c = 0; c < 9; c++)
			{
				if(tot[c] == 1)
                {
                    for (int d = 0; d < 3; d++)
					{
                        for (int e = 0; e < 3; e++)
                        {
                            if(solv[startrow+d][startcol+e].getCell(c))
                            {
                                //System.out.println("GRID: Changed (" + (startrow+d+1) + "," + (startcol+e+1) + ") to " + (c+1));
                                if(this.guessed.size()!=0) { this.changed.add(new SolverType('c',startrow+d,startcol+e,(double)(c+1), null)); }
                                this.puzzle.setCell(startrow+d,startcol+e,(double)(c+1));
                                return true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
    
    /**Check whether a single solution in a row or column*/
    Boolean checkrowposs(SolverData[][] solv,String rowcol)
    {
        for(int i = 0; i < 9; i++)
    	{
			int[] tot = {0,0,0,0,0,0,0,0,0};
    		for(int j = 0; j < 9; j++)
    		{
   				for(int c = 0; c < 9; c++)
   				{
                    if(rowcol.equals("row"))
                    {
                        if(solv[i][j].getCell(c))
                        {
                            tot[c] = tot[c]+1;
                        }
                    }
                    if(rowcol.equals("col"))
                    {
                        if(solv[j][i].getCell(c))
                        {
                            tot[c] = tot[c]+1;
                        }
                    }
   				}
    		}
    		for(int c = 0; c < 9; c++)
			{
				if(tot[c] == 1)
				{
					for (int d = 0; d < 9; d++)
					{
						if(rowcol.equals("row"))
                        {
                            if(solv[i][d].getCell(c))
                            {
                                if(this.guessed.size()!=0) { this.changed.add(new SolverType('c',i,d,(double)(c+1),null)); }
                                this.puzzle.setCell(i,d,(double)(c+1));
                                return true;
                            }
                        }
                        else if(rowcol.equals("col"))
                        {
                            if(solv[d][i].getCell(c))
                            {
                                if(this.guessed.size()!=0) { this.changed.add(new SolverType('c',d,i,(double)(c+1), null)); }
                                this.puzzle.setCell(d,i,(double)(c+1));
                                return true;
                            }
						}
					}
				}
			}
		}
        return false;
    }

    
    /**Calculate start row from input*/
    int workoutstartrow(int i)
    {
    	if(i < 3) { return 0; }
    	else if(i < 6) { return 3; }
    	else { return 6; }
    }
}
